// Iterator.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define null 0
struct TreeNode
{
    int value;
    TreeNode *left, *right;

    TreeNode() { };

    TreeNode(int v)
    {
        value=v;
        left=right=null;
    };
};

class BTreeIterator
{
private:
    stack<TreeNode *> s;
    TreeNode *root;
    TreeNode *current;
    TreeNode *previous;
    int order;
    int last;

public:
    BTreeIterator(TreeNode *p, int iOrder) // 0:pre-order, 1:in-order, 2:post-order
    {
        if(!p||iOrder<0||iOrder>2) throw;

        while(!s.empty()) s.pop();
        root=p;
        current=null;
        previous=null;
        order=iOrder;
        last=0; // 0:from up, 1:from left, 2:from right
    }
    ~BTreeIterator()
    {
        while(!s.empty()) s.pop();
    }

    TreeNode *Previous();
    TreeNode *Current();
    TreeNode *Next();
};

TreeNode *BTreeIterator::Previous()
{
    return previous;
}

TreeNode *BTreeIterator::Current()
{
    return current;
}

TreeNode *BTreeIterator::Next()
{
    if(s.empty())
    {
        if(current) return null; // when current is the last node, return NULL as the Next

        last=0;
        s.push(root);
    }

    while(!s.empty())
    {
        TreeNode *p=s.top();
        if(last==0)
        {
            if(order==0 && current!=p)
            {
                previous=current;
                current=p;
                return p;
            }

            if(p->left)
            {
                last=0;
                s.push(p->left);
            }
            else last=1;
        }
        else if(last==1)
        {
            if(order==1 && current!=p)
            {
                previous=current;
                current=p;
                return p;
            }

            if(p->right)
            {
                last=0;
                s.push(p->right);
            }
            else last=2;
        }
        else if(last==2)
        {
            if(order==2 && current!=p)
            {
                previous=current;
                current=p;
                return p;
            }

            s.pop();
            if(!s.empty() && s.top()->left==p) last=1;
            else last=2;
        }
    }

    return null;
}

int _tmain(int argc, _TCHAR* argv[])
{
    TreeNode *p=new TreeNode(100);
    p->left=new TreeNode(50);
    p->right=new TreeNode(150);

    p->left->left=new TreeNode(25);
    p->left->right=new TreeNode(75);
    p->left->right->left=new TreeNode(65);

    p->right->left=new TreeNode(125);
    p->right->right=new TreeNode(175);
    p->right->left->left=new TreeNode(110);
    p->right->left->left->right=new TreeNode(115);

    int order=1; // 0:pre-order, 1:in-order, 2:post-order
    BTreeIterator it=BTreeIterator(p,order);
    while(TreeNode *node=it.Next())
    {
        cout<<node->value<<" ";
    }

    return getchar();
}

